2.4 KB · ⇊ 2 parts · ⤓ Micron 2.4 KB · ⤓ HTML 7.7 KB

top

In computational geometry, the largest empty sphere problem is the problem of finding a hypersphere of largest radius in d-dimensional space whose interior does not overlap with any given obstacles.

• Two dimensions

• See also

• References

The largest empty circle problem is the problem of finding a circle of largest radius in the plane whose interior does not overlap with any given obstacles.

A common special case is as follows. Given n points in the plane, find a largest circle centered within their convex hull and enclosing none of them. The problem may be solved using Voronoi diagrams in optimal time Θ Θ ( n log n ) {\displaystyle \Theta (n\,\log \,n)} .cite-ref-1[1]cite-ref-2[2]

• Bounding sphere

• Farthest-first traversal

• Largest empty rectangle

cite-note-11. ↑ G. T. Toussaint, "Computing largest empty circles with location constraints," International Journal of Computer and Information Sciences, vol. 12, No. 5, October, 1983, pp. 347-358.

cite-note-22. ↑ Megan Schuster, "The Largest Empty Circle Problem"